package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.*;

/**
 * @author zhangjy
 * @description 对称二叉树
 * @date 2025/4/9 9:34
 */
public class IsSymmetric_1010 {

    /**
     * 个解：dfs-迭代（参考官解）
     * <p>
     * 思路：两个队列占用空间，那就一个队列，出队时直接比较root左右子树镜像节点值；
     * 使用栈也是同样思路，逻辑没有更改，也是一次弹出两个元素比较，然后镜像入栈。
     * <p>
     * 时间复杂度：T(n) = O(n)；其中，n是节点个数，因为遍历了整棵树。
     * 空间复杂度：S(n) = O(n)；这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。
     */
    public boolean isSymmetric5(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            TreeNode q = queue.poll();
            // p、q都空，是轴对称
            if (p == null && q == null) continue;

            // p空，q非空
            if (p == null) return false;
            // p非空，q空
            if (q == null) return false;
            // p、q非空且值不等
            if (p.val != q.val) return false;

            // 走到这里，p、q一定非空且节点值相等，满足轴对称，所以继续向下判断
            // 镜像入队，保证比较时在判断镜像节点的节点值
            // p左、q右
            queue.offer(p.left);
            queue.offer(q.right);

            // p右、q左
            queue.offer(p.right);
            queue.offer(q.left);
        }

        return true;
    }

    /**
     * 个解：dfs-迭代；
     * 用到两个队列，占用空间过多，可参考官解优化。
     */
    public boolean isSymmetric4(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> leftQueue = new LinkedList<>();
        Queue<TreeNode> rightQueue = new LinkedList<>();
        leftQueue.offer(root.left);
        rightQueue.offer(root.right);
        while (!leftQueue.isEmpty() || !rightQueue.isEmpty()) {
            TreeNode left = leftQueue.poll();
            TreeNode right = rightQueue.poll();
//            if (left == null && right == null) return true;

            if (left == null && right != null) return false;
            if (left != null && right == null) return false;
            if ((left != null && right != null) && (left.val != right.val)) return false;

            // 保证root的左右子树是镜像入队
            if (left != null && right != null) {
                leftQueue.offer(left.left);
                rightQueue.offer(right.right);

                leftQueue.offer(left.right);
                rightQueue.offer(right.left);
            }
        }

        return true;
    }

    /**
     * dmsxl解法：dfs-递归；
     * <p>
     * 思路：
     * 考虑【遍历顺序】——本题递归，采用类似后序遍历的方式（并不是严格后序）；
     * <p>
     * 这里，需要判断root是否镜像对称，要把左子树、右子树分别处理完，知道它们是否互为镜像对称，才能返回根节点root，知道它是否为镜像对称。
     * 什么情况要用到后序遍历？——需要收集孩子信息，向上一层返回结果。
     */
    public boolean isSymmetric3(TreeNode root) {
        if (root == null) return true;
        return symmetric3(root.left, root.right);
    }

    public boolean symmetric3(TreeNode p, TreeNode q) {
        // p、q都空，是轴对称
        if (p == null && q == null) return true;

        // p空，q非空
        if (p == null) return false;
        // p非空，q空
        if (q == null) return false;
        // p、q都非空，且值不等
        if (p.val != q.val) return false;

        // 走到这里一定有，p、q都不空且节点值不相等，此时才往下一层递归；这里相比个解dfs（也就是官解），在非轴对称情况下会少一些向下递归，因为节点值不同就直接返回了，而不是递归完才判断节点值
        // 后序
        // 左
        boolean first = symmetric3(p.left, q.right);
        // 右
        boolean second = symmetric3(p.right, q.left);

        // 中
        return first && second;
    }

    /**
     * 个解：dfs-递归-（参考dmsxl，结果这里写出来的实际解法同官解一样）
     * <p>
     * 思路：
     * 如果一个树的左子树与右子树镜像对称，那么这个树是对称的。因此，该问题可以转化为：两个树在什么情况下互为镜像？
     * <p>
     * 如果同时满足下面的条件，两个树互为镜像：
     * <p>
     * 1.它们的两个根结点具有相同的值
     * 2.每个树的右子树都与另一个树的左子树镜像对称
     * <p>
     * 所以，这里转化为判断根节点root的左右子树是否互为镜像；
     * 注意，每层递归不是只处理一个节点，而是同时处理两棵树。
     */
    public boolean isSymmetric2(TreeNode root) {
        if (root == null) return true;
        return symmetric2(root.left, root.right);
    }

    public boolean symmetric2(TreeNode p, TreeNode q) {
        // 递归这里逻辑中，的p、q并不是同一个父节点的左右孩子，而是不同根节点的镜像节点
        // p、q都空，是轴对称
        if (p == null && q == null) return true;

        // p空，q非空
        if (p == null) return false;
        // p非空，q空
        if (q == null) return false;
        // 这里不判断节点值，因为我认为，如果按照后序遍历，那么每层最后需要去处理节点值，在这里就包含判断节点值是否相等
        // p、q都非空，且值不等
//        if (p.val != q.val) return false;

        // 走到这里一定有，p、q都不空，还需判断镜像节点值
        // 后序
        // 左
        boolean first = symmetric2(p.left, q.right);
        // 右
        boolean second = symmetric2(p.right, q.left);

        // 中
        return first && second && (p.val == q.val);
    }

    // 该方法有误
//    public boolean symmetric2(TreeNode left, TreeNode right)  {
//        // left、right都空，是轴对称
//        if (left == null && right == null) return true;
//
//        // left空，right非空
//        if (left == null) return false;
//        // left非空，right空
//        if (right == null) return false;
//        // left、right都非空，且值不等
//        if (left.val != right.val) return false;
//
//        boolean first = symmetric2(left.left, right.right);
//        boolean second = symmetric2(left.right, right.left);
//
//        // 镜像子树的判断结果
//        return first && second;
//    }

    /**
     * 个解：BFS-迭代。
     * <p>
     * 思路：
     * <p>
     * 1.判断每层是否对称（若每层镜像节点值相等，则对称；反之，不对称）。
     * <p>
     * 2.当前节点的孩子是null也要入队；为了上面通过镜像值判断，孩子空节点值就记录为null。
     * <p>
     * T(n) = O(n)；其中，n为节点个数，每个节点会被访问一次且只会被访问一次，即从队列中弹出。
     * S(n) = O(n)；其中，n为每层节点个数，每层节点要出入队一次，节点值也会记录一次。
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 记录每层节点值
            int levelSize = queue.size();
            List<Integer> levelVals = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode poll = queue.poll();
                levelVals.add(poll == null ? null : poll.val);

                // 当前节点孩子若空也入队
                if (poll != null) {
                    queue.offer(poll.left);
                    queue.offer(poll.right);
                }
            }

            // 校验每层是否对称
            for (int i = 0; i < levelSize / 2; i++) {
                Integer left = levelVals.get(i);
                Integer right = levelVals.get(levelSize - 1 - i);
                // 左右镜像节点值不同，则不对称
                if (left != right) return false;
            }
        }

        return true;
    }

}
